/*
 * @lc app=leetcode.cn id=752 lang=typescript
 *
 * [752] 打开转盘锁
 */

// @lc code=start

class Data {
  constructor(public s: string = '', public l: number = 0) {
    this.s = s;
    this.l = l;
  }
}

function openLock(deadends: string[], target: string): number {
  const deadLock = new Set([...deadends]);
  // 开始位置是否是死锁
  if (deadLock.has('0000')) return -1;

  const getStr = (s: string, i: number, j: number): string => {
    const arr = s.split('');
    let next: number;
    switch (j) {
      case 0:
        next = Number(arr[i]) + 1 > 9 ? 0 : Number(arr[i]) + 1;
        arr[i] = String(next);
        break;
      case 1:
        next = Number(arr[i]) - 1 < 0 ? 9 : Number(arr[i]) - 1;
        arr[i] = String(next);
        break;
    }
    return arr.join('');
  };

  const queue: Data[] = [];
  deadLock.add('0000');
  queue.push(new Data('0000', 0));
  while (queue.length) {
    const data = queue.shift();
    if (data.s === target) return data.l;
    // 搜索其他状态
    // 4位数，每个数字2种状态：加1或者减1
    for (let i = 0; i < 4; i++) {
      for (let j = 0; j < 2; j++) {
        const temp = getStr(data.s, i, j);
        if (deadLock.has(temp)) continue;
        deadLock.add(temp);
        queue.push(new Data(temp, data.l + 1));
      }
    }
  }

  return -1;
}
// @lc code=end
